Increasing data locality and introducing Level-3 BLAS in the Neville elimination

In this paper we present two new algorithmic variants to compute the Neville elimination, with and without pivoting, which improve data locality and cast most of the computations in terms of high-performance Level 3 BLAS. The experimental evaluation on a state-of-the-art multi-core processor demonstrates that the new blocked algorithms exhibit a much higher degree of concurrency and better cache usage, yielding higher performance while offering numerical accuracy akin to that of the traditional columnwise variant in most cases.     

Minimizing the number of machines for minimum length schedules

In this paper, we present a new objective function for scheduling on parallel machines: minimizing the number of machines for schedules of minimum length. We study its complexity and we prove the NP-completeness of this problem, even if there is no precedences or for unitary execution times. We propose several polynomial algorithms for various particular cases.     

Mixed parallel processors with interdependent blocking

This paper studies a system of parallel service facilities or processors with mixed exponential and non-exponential queues, a non-exponential finite source input and interdependent arrival as well as departure blocking such as due to a common pool or shared resource. A concrete invariance condition upon the blocking protocol is provided. Under this condition the stationary busy source distribution is shown to be of an insensitive product form. The result unifies and extends known product form results as will be illustrated by several examples.     

Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays

This paper addresses a certain type of scheduling problem that arises when a parallel computation is to be executed on a set of identical parallel processors. It is assumed that if two precedence-related tasks are processed on two different processors, due to the information transferring, there will be a task-dependent communication delay between them. For each task, a processing time, a due date and a weight is given while the goal is to minimize the total weighted late work. An integer linear mathematical programming model and a branch-and-bound algorithm have been developed for the proposed problem. Comparing the results obtained by the proposed branch-and-bound algorithm with those obtained by CPLEX, indicates the effectiveness of the method.     

Optical-digital processors for morphological and rank order filtering

Non-linear rank order and morphological filtering can be achieved in optical-digital processors. In these processors, all convolutions are performed in inherently parallel optical correlators. Arithmetic and logic operations are made digitally. Due to the threshold decomposition concept, grey scale images are sequentially treated slice by slice. The optical-digital method of local histogram calculation within both binary and weighted neighbourhoods allows local non-linear operations. We derive rank order and morphological filters from optically calculated convolutions. Several configurations of optical convolvers are discussed. Further improvements in the technology of spatial light modulators and encoded light sources are needed before these processors' practical uses will appear.     

Picosecond laser pulse correlation by using a molecular dye

Summary We present a new, simple and cost effective scheme for the measure of the second-order correlation function of Nd-YAG laser second-harmonic (532 nm) pulses. We measure the transmission of a probe beam in a cell containing 6G-Rhodamine solution bleached by a counterpropagating pump beam. Under a convenient choice of experimental parameters, we can measure also the contribution of third-order correlation function.     

Little-Preemptive Scheduling on Unrelated Processors

We consider the preemptive scheduling of n independent jobs on m unrelated machines to minimize the makespan. Preemptive schedules with at most 2m–3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m–1 preemptions. This is better than the earlier known best bound of 4m ²–5m+2 on the total number of preemptions. Without the restriction on the maximal job processing time, our (2m–3)-preemptive schedules have a makespan which is no more than either of the following two magnitudes: (a) the maximum between the longest job processing time and the optimal preemptive makespan, and (b) the optimal nonpreemptive makespan. Our (m–1)-preemptive schedules might be at most twice worse than an optimal one.     

Spatial phase coding for incoherent optical processors

In this paper we introduce spatial phase coding of incoherent optical signals for representing signed numbers in optical processors and present an experimental demonstration of this coding technique. If a diffraction grating, such as an acousto-optic cell, modulates a stream of light, the image of the grating can be recovered from the diffracted beam. The position of the grating image, or more precisely its phase, can be used to denote the sign of the number represented by the diffracted light. The intensity of the light represents the magnitude of the number. This technique is more economical than current methods in terms of the number of information channels required to represent a number and the amount of post processing required.     

A duality approach to admission and scheduling controls of queues

This paper studies theadmission andscheduling control problem in anM/M/2 queueing system with nonidentical processors. Admission control renders when a newly arrived job should be accepted, whereas scheduling control determines when an available processor should be utilized. The system received a rewardR when a job completes its service and pays a unit holding costC while a job is in the system. The main goal of the paper is to obtain the admission/scheduling policy that maximizes the expected discounted and long-run average profits (reward minus cost). We convert the system into its dual, a stochastically identical system subject toexpulsion/scheduling control, and prove that the individually optimal policy in the dual system is socially optimal in the original system. In contrast with the dynamic programming (DP) technique which considers the system as a whole, we adopt the viewpoint of an individual job and analyze the impact of its behavior on the social outcome. The key properties which simplify the analysis are that under the individually optimal policy the profit of a job under the preemptive last-come first-priority service discipline (LCFP-P) is independent of jobs arrived earlier than itself and that the system is insensitive to service discipline imposed. The former makes possible to bypass complex dynamic programming analyses and the latter serves as a vehicle in connecting the social and individual optimality. We also exploit system operational characteristics under LCFP-P to obtain simple and close approximations of the optimal thresholds.     

Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem

We consider the generalization of the classical P||C_max problem (assign n jobs to m identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2. We briefly survey lower and upper bounds from the literature. We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria.